package com.company.剑指offer每日刷题.专项版;

/**
 * 给定两个整数 a 和 b ，求它们的除法的商 a/b ，要求不得使用乘号 '*'、除号 '/' 以及求余符号 '%'
 * 注意：
 * <p>
 * 整数除法的结果应当截去（truncate）其小数部分，例如：truncate(8.345) = 8以及truncate(-2.7335) = -2
 * 假设我们的环境只能存储 32 位有符号整数，其数值范围是 [−231,231−1]。本题中，如果除法结果溢出，则返回 2^31− 1
 * <p>
 * 示例 1：
 * <p>
 * 输入：a = 15, b = 2
 * 输出：7
 * 解释：15/2 = truncate(7.5) = 7
 * <p>
 * 来源：力扣（LeetCode）
 * 链接：https://leetcode-cn.com/problems/xoh6Oh
 * 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
 */
public class Divide {
    public static void main(String[] args) {
        Divide divide = new Divide();
        System.out.println(divide.divide(35,6));
    }


    /**
     * 方法：减法代替除法
     * 思路：  用被减数减去若干次减数，这个次数也就是整数除法的值
     * 关于将a,b全部转成正数的考虑：
         *  因为 当a >0 时，  a>>i,不论i是多少，这个a>>i都不会出问题，虽然b<<i会溢出，但是可以将它转化为a >>i
         *  但是 当a<0时，i足够大，a>>i和a<<i就都变得不可靠了。这样的问题就变得很复杂
     *
     * 注意：      int的范围是   -2^31 ~ 2^31-1
     */
    public int divide(int a, int b) {
        //先排除边界情况
        if (a == Integer.MIN_VALUE && b == -1) {
            return Integer.MAX_VALUE;
        }
        int sign = (a > 0) ^ (b > 0) ? -1 : 1;
        a = Math.abs(a);
        b = Math.abs(b);
        int res = 0;
        for (int i = 31; i >= 0; i--) {
            //因为a 和 b 等于 -2147483648 时 Math.abs(a或b) 的值还是  -2147483648， 所以要解决这个"bug"
            //1. 避免b<<i溢出，将a >= (b<<i) 变形为 (a>>i) >= b  （不等式的知识了..）
            //2. 考虑a可能等于-2147483648，所以采用>>> ， 变形为(a>>>i) >=b
            //3. 考虑 b可能等于-2147483648，所以变形为  (a>>>i)-b>=0，
            if ((a >>> i) - b >= 0) {
                a -= (b << i);
                res += (1 << i);
            }
        }
        return sign > 0 ?res:-res;
    }
}
